package main

import (
	"fmt"
	"math"
)

func main() {

	////图1
	//addEdge(1, 2, 3)
	//addEdge(1, 3, 2)
	//addEdge(2, 3, 1)
	//addEdge(2, 4, 3)
	//addEdge(2, 5, 4)
	//addEdge(3, 5, 2)
	//addEdge(4, 6, 2)
	//addEdge(5, 6, 3)

	//图2
	addEdge(1, 2, 4)
	addEdge(1, 3, 2)
	addEdge(2, 3, 1)
	addEdge(2, 4, 2)
	addEdge(2, 5, 4)
	addEdge(3, 5, 2)
	addEdge(4, 6, 3)
	addEdge(5, 6, 3)

	f := maxFlow(1, 6)
	fmt.Println("最大流：", f)

}

/*
网络图 -- 最大流


奇妙技巧：
x是偶数，那么x^1就是x的下一个奇数 (x,x^1)
x是奇数，那么x^1就是x的上一个偶数 (x^1,x)
x和x^1永远是奇偶互相成对出现！！！
0 1
1 0
2 3
3 2
4 5
5 4
*/

type edge struct {
	u, v      int
	cap, flow float64
}

const maxN = 10000

var edges []edge    //保存所有边，其他变量存储边的编号
var g [maxN][]int   //点的所有出边在edges中的编号
var a [maxN]float64 //点的入边在增广路径上能通过的最小流
var p [maxN]int     //点的入边编号

var n, m int //点数，边数
func addEdge(u, v int, cap float64) {
	edges = append(edges, edge{
		u:    u,
		v:    v,
		cap:  cap,
		flow: 0,
	})
	edges = append(edges, edge{
		u:    v,
		v:    u,
		cap:  0,
		flow: 0,
	})
	m = len(edges)
	g[u] = append(g[u], m-2)
	g[v] = append(g[v], m-1)
}

func maxFlow(s, t int) (flow float64) {
	for {
		a = [maxN]float64{} //重置a

		//bfs找增广路径
		q := []int{s}
		a[s] = math.Inf(1) //“引子”，源点初始流无穷大；这是递推的起步
		for len(q) != 0 {
			u := q[0]
			q = q[1:]
			for i := 0; i < len(g[u]); i++ {
				e := edges[g[u][i]]
				//一个点可能有多条入边指向它，这里只要处理过一次就不再重复处理这个点，因为每次bfs只要找到一条增光路径即可
				if a[e.v] == 0 && e.cap > e.flow {
					q = append(q, e.v)
					a[e.v] = min(a[u], e.cap-e.flow)
					p[e.v] = g[u][i]
				}
			}
			if a[t] != 0 {
				break
			}
		}

		if a[t] == 0 {
			break //无增广路径，算法结束
		}
		//处理找到的增广路径
		for i := t; i != s; i = edges[p[i]].u {
			edges[p[i]].flow += a[t]   //正向路径叠加flow
			edges[p[i]^1].flow -= a[t] //反向路径叠减flow
		}
		flow += a[t]
	}
	return
}
